package com.dyz.baseAlgorithm.searchAlgorithm;


import java.util.ArrayList;
import java.util.List;

/**
 * @author: daiyizheng
 * @date: 2021/5/13 12:56
 * @description:
 */
public class BinarySearch {
    public static void main(String[] args) {

        int arr[] = { 1, 8, 10, 89, 1000, 1234 };
        int resIndex = binarySearch(arr, 0, arr.length - 1, 1000);
        System.out.println("resIndex=" + resIndex);

    }
    public static  int binarySearch(int [] arr, int left, int right, int value){
        //二分查找

        if(left>right){
            return -1;
        }
        int mid = (left + right) / 2;
        int midVal = arr[mid];
        if (value> midVal){
            return binarySearch(arr, mid+1, right, value);
        }else if (value < midVal){
            return binarySearch(arr, left, mid-1, value);
        }else {
            return mid;
        }
    }

    public static List<Integer> binarySearchAll(int [] arr, int left, int right, int value) {
        //当left > right 时，说明递归整个数组，但是没有找到
        if (left > right) {
            return new ArrayList<Integer>();
        }
        int mid = (left + right) / 2;
        int midVal = arr[mid];

        if (value > midVal) {
            return binarySearchAll(arr, mid + 1, right, value);
        } else if (value < midVal) {
            return binarySearchAll(arr, left, mid - 1, value);
        } else {
            //思路分析
            //1. 在找到mid 索引值，不要马上返回
            //2. 向mid索引值的左边扫描，将所有满足1000，的元素的下标，加入到集合ArrayList
            //3. 向mid索引值的右边扫描，将满足1000的元素的下标，加入到集合ArrayList
            //4. 将ArrayList返回

            List<Integer> resIndexList = new ArrayList<Integer>();
            // 向mid 索引值的左边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
            int temp = mid - 1;
            while (true) {
                if (temp < 0 || arr[temp] != value) {
                    break;
                }
                //// 否则，就temp 放入到 resIndexlist
                resIndexList.add(temp);
                temp -= 1;
            }
            resIndexList.add(mid); //
            // 向mid 索引值的右边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
            temp = mid + 1;
            while (true) {
                if (temp > arr.length - 1 || arr[temp] != value) {// 退出
                    break;
                }
                // 否则，就temp 放入到 resIndexlist
                resIndexList.add(temp);
                temp += 1; // temp右移
            }
            return resIndexList;

        }
    }
}
